1 /*
2 * TouchGraph LLC. Apache-Style Software License
3 *
4 *
5 * Copyright (c) 2001-2002 Alexander Shapiro. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
17 * distribution.
18 *
19 * 3. The end-user documentation included with the redistribution,
20 * if any, must include the following acknowledgment:
21 * "This product includes software developed by
22 * TouchGraph LLC (http://www.touchgraph.com/)."
23 * Alternately, this acknowledgment may appear in the software itself,
24 * if and wherever such third-party acknowledgments normally appear.
25 *
26 * 4. The names "TouchGraph" or "TouchGraph LLC" must not be used to endorse
27 * or promote products derived from this software without prior written
28 * permission. For written permission, please contact
29 * alex@touchgraph.com
30 *
31 * 5. Products derived from this software may not be called "TouchGraph",
32 * nor may "TouchGraph" appear in their name, without prior written
33 * permission of alex@touchgraph.com.
34 *
35 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
36 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
37 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
38 * DISCLAIMED. IN NO EVENT SHALL TOUCHGRAPH OR ITS CONTRIBUTORS BE
39 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
40 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
41 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
42 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
43 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
44 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
45 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
46 * ====================================================================
47 *
48 */
49
50 package com.touchgraph.graphlayout.graphelements;
51
52 import java.util.*;
53
54 import com.touchgraph.graphlayout.*;
55
56 /*** GESUtils is a set of functions that return information about a GraphEltSet
57 *
58 * @author Alexander Shapiro
59 * @version 1.21 $Id: GESUtils.java,v 1.1.1.1 2004/02/06 08:44:05 keesj Exp $
60 */
61 public class GESUtils {
62
63 /*** Returns a hashtable of Node-Integer pairs, where integers are the minimum
64 * distance from the focusNode to any given Node, and the Nodes in the Hashtable
65 * are all within radius distance from the focusNode.
66 *
67 * Nodes with edge degrees of more then maxAddEdgeCount are not added to the hashtable, and those
68 * with edge degrees of more then maxExpandEdgeCount are added but not expanded.
69 *
70 * If unidirectional is set to true, then edges are only follewed in the forward direction.
71 *
72 */
73
74 public static Hashtable calculateDistances(GraphEltSet ges, Node focusNode, int radius,
75 int maxAddEdgeCount, int maxExpandEdgeCount,
76 boolean unidirectional ) {
77 Hashtable distHash = new Hashtable();
78 distHash.put(focusNode,new Integer(0));
79
80 TGNodeQueue nodeQ = new TGNodeQueue();
81 nodeQ.push(focusNode);
82
83 while (!nodeQ.isEmpty()) {
84 Node n = nodeQ.pop();
85 int currDist = ((Integer) distHash.get(n)).intValue();
86
87 if (currDist>=radius) break;
88
89 for (int i = 0 ; i < n.edgeCount(); i++) {
90 Edge e=n.edgeAt(i);
91 if(n!=n.edgeAt(i).getFrom() && unidirectional) continue;
92 Node adjNode = e.getOtherEndpt(n);
93 if(ges.contains(e) && !distHash.containsKey(adjNode) && adjNode.edgeCount()<=maxAddEdgeCount) {
94 if (adjNode.edgeCount()<=maxExpandEdgeCount) nodeQ.push(adjNode);
95 distHash.put(adjNode,new Integer(currDist+1));
96 }
97 }
98 }
99 return distHash;
100 }
101
102 public static Hashtable calculateDistances(GraphEltSet ges, Node focusNode, int radius ) {
103 return calculateDistances(ges, focusNode, radius, 1000, 1000, false);
104 }
105
106 /*** A temporary function that returns the largest connected subgraph in a GraphEltSet.
107 */
108
109 public static Collection getLargestConnectedSubgraph(GraphEltSet ges) {
110 int nodeCount = ges.nodeCount();
111 if(nodeCount==0) return null;
112
113 Vector subgraphVector = new Vector();
114 for(int i=0; i<nodeCount; i++) {
115 Node n = ges.nodeAt(i);
116 boolean skipNode=false;
117 for (int j = 0; j<subgraphVector.size();j++) {
118 if(((Collection) subgraphVector.elementAt(j)).contains(n)) {
119 skipNode=true;
120 }
121 }
122 Collection subgraph = calculateDistances(ges,n,1000).keySet();
123 if(subgraph.size()>nodeCount/2) return subgraph; //We are done
124 if (!skipNode) subgraphVector.add(subgraph);
125
126 }
127
128 int maxSize=0;
129 int maxIndex=0;
130 for (int j = 0; j<subgraphVector.size();j++) {
131 if(((Collection) subgraphVector.elementAt(j)).size()>maxSize) {
132 maxSize = ((Collection) subgraphVector.elementAt(j)).size();
133 maxIndex = j;
134 }
135 }
136
137 return (Collection) subgraphVector.elementAt(maxIndex);
138 }
139
140 } // end com.touchgraph.graphlayout.graphelements.GraphEltSet